package com.javabasic.algorithm.sword_of_offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @author xiongmin
 * @version 0.0.1
 * @description Created by work on 2021/10/17 2:29 下午
 * @see [Leetcode 230](https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/)
 */
public class 二叉搜索树中第K小的元素 {

    List<Integer> elementList = new ArrayList<>(16);

    /**
     * 方法一：暴力法【二叉树转为有序数组再获取下标对应的元素】
     * @param root
     * @param k
     * @return
     */
     public int kthSmallest1(TreeNode root, int k) {
         getKthElementArray(root);
         return elementList.get(k-1);
     }

     private void getKthElementArray(TreeNode root) {
         if (root != null) {
             getKthElementArray(root.left);
             elementList.add(root.val);
             getKthElementArray(root.right);
         }
     }


    int index;
    boolean find = false;
    int result = -1;
    int tag = 0;
    /**
     * 方法二：通过递归+全局变量记录索引的位置，找到结果之后再快速剪枝，返回结果、提高效率，
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode root, int k) {
        index = k;
        getKthElement(root);
        return result;
    }

    private void getKthElement(TreeNode root) {
        if (!find && root != null) {
            getKthElement(root.left);
            tag++;
            System.out.println("tag = " + tag + " value = " + root.val);
            if (tag == index) {
                find = true;
                result = root.val;
            }
            getKthElement(root.right);
        }
    }



}
